home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph / _g_random.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  12.1 KB  |  544 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _g_random.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/graph.h>
  17. #include <LEDA/ugraph.h>
  18.  
  19.  
  20. void random_graph(graph& G, int n, int m)
  21. { /* random graph with n nodes and m edges */ 
  22.  
  23.  int i;
  24.  node* V = new node[n];
  25.  G.clear();
  26.  for(i=0;i<n;i++) V[i] = G.new_node();
  27.  
  28.  while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  29.  
  30. /*
  31.  int deg = m/n;
  32.  int r = m%n;
  33.  int k;
  34.  for(i=0;i<n;i++)
  35.    for(k=0;k<deg;k++)
  36.       G.new_edge(V[i],V[random(0,n-1)]);
  37.  while (r--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  38. */
  39.  
  40. }
  41.  
  42. void random_ugraph(ugraph& G, int n, int m)
  43. { int i;
  44.  node* V = new node[n];
  45.  G.clear();
  46.  for(i=0;i<n;i++) V[i] = G.new_node();
  47.  while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  48. }
  49.  
  50. void random_bigraph(graph& G,int n1,int n2,int m,list<node>& A,list<node>& B)
  51. {
  52.    int  d = m/n1; 
  53.    int  r = m%n1; 
  54.  
  55.    node* AV = new node[n1];
  56.    node* BV = new node[n2];
  57.  
  58.    A.clear();
  59.    B.clear();
  60.    G.clear();
  61.  
  62.    for(int a = 0; a < n1; a++)  A.append(AV[a] = G.new_node());
  63.    for(int b = 0; b < n2; b++)  B.append(BV[b] = G.new_node());
  64.  
  65.    node v;
  66.    int i;
  67.  
  68.    forall(v,A)
  69.      for(i=0;i<d;i++)
  70.        G.new_edge(v,BV[random(0,n2-1)]);
  71.  
  72.    while (r--) G.new_edge(AV[random(0,n1-1)], BV[random(0,n2-1)]);
  73.  
  74. }
  75.  
  76.  
  77.  
  78.  
  79. //------------------------------------------------------------------------------
  80. // random planar graph
  81. //------------------------------------------------------------------------------
  82.  
  83. #include <LEDA/sortseq.h>
  84. #include <LEDA/prio.h>
  85. #include <math.h>
  86.  
  87.  
  88. #define EPS  0.00001
  89. #define EPS2 0.0000000001
  90.  
  91. class POINT;
  92. class SEGMENT;
  93. typedef POINT* point;
  94. typedef SEGMENT* segment;
  95.  
  96. enum point_type {Intersection=0,Rightend=1,Leftend=2}; 
  97.  
  98. class POINT
  99. {
  100.   friend class SEGMENT;
  101.  
  102.   segment seg;
  103.   int     kind;
  104.   double  x;
  105.   double  y;
  106.  
  107.   public:
  108.  
  109.   POINT(double a,double b)  
  110.   { 
  111.     x=a; y=b; seg=0; kind=Intersection;
  112.    }
  113.  
  114.  
  115.   LEDA_MEMORY(POINT);
  116.  
  117.   friend double    get_x(point);
  118.   friend double    get_y(point);
  119.   friend int       get_kind(point);
  120.   friend segment get_seg(point);
  121.  
  122.   friend bool intersection(segment, segment, point&);
  123. };
  124.  
  125. inline double    get_x(point p)    { return p->x; }
  126. inline double    get_y(point p)    { return p->y; }
  127. inline int       get_kind(point p) { return p->kind; }
  128. inline segment get_seg(point p)  { return p->seg; }   
  129.  
  130.  
  131.  
  132. static int compare(point& p1,point& p2)
  133. { if (p1==p2) return 0;
  134.  
  135.   double diffx = get_x(p1) - get_x(p2);
  136.   if (diffx >  EPS2 ) return  1;
  137.   if (diffx < -EPS2 ) return -1;
  138.  
  139.   int    diffk = get_kind(p1)-get_kind(p2);
  140.   if (diffk != 0) return diffk;
  141.  
  142.   double diffy = get_y(p1) - get_y(p2);
  143.   if (diffy >  EPS2 ) return  1;
  144.   if (diffy < -EPS2 ) return -1;
  145.  
  146.   return 0;
  147.  
  148. }
  149.  
  150.  
  151. class SEGMENT
  152. {
  153.   point startpoint;
  154.   point endpoint;
  155.   double  slope;
  156.   double  yshift;
  157.   node  left_node;
  158.   int   orient;
  159.   int   color;
  160.   int   name;
  161.  
  162.  
  163.   public:
  164.  
  165.   SEGMENT(point, point,int,int);     
  166.  
  167.  ~SEGMENT() { delete startpoint; delete endpoint; }     
  168.  
  169.   LEDA_MEMORY(SEGMENT);
  170.  
  171.   friend point get_startpoint(segment);
  172.   friend point get_endpoint(segment);
  173.   friend double get_slope(segment);
  174.   friend double get_yshift(segment);
  175.   friend int  get_orient(segment);
  176.   friend int  get_color(segment);
  177.   friend int  get_name(segment);
  178.   friend node get_left_node(segment);
  179.   friend void set_left_node(segment, node);
  180.  
  181.   friend bool intersection(segment, segment, point&);
  182. };
  183.  
  184.  
  185. inline point get_startpoint(segment seg)     { return seg->startpoint; }
  186. inline point get_endpoint(segment seg)       { return seg->endpoint; }
  187. inline double get_slope(segment seg)           { return seg->slope; }
  188. inline double get_yshift(segment seg)          { return seg->yshift; }
  189. inline int  get_orient(segment seg)            { return seg->orient; }
  190. inline int  get_color(segment seg)             { return seg->color; }
  191. inline int  get_name(segment seg)              { return seg->name; }
  192. inline node get_left_node(segment seg)         { return seg->left_node; }
  193. inline void set_left_node(segment seg, node v) { seg->left_node = v; }
  194.  
  195.  
  196.  
  197. SEGMENT::SEGMENT(point p1,point p2,int c, int n)    
  198.   {
  199.     left_node  = nil;
  200.     color      = c;
  201.     name       = n;
  202.  
  203.     if (compare(p1,p2) < 0)
  204.      { startpoint = p1; 
  205.        endpoint = p2; 
  206.        orient = 0;
  207.       }
  208.     else
  209.      { startpoint = p2; 
  210.        endpoint = p1; 
  211.        orient = 1;
  212.       }
  213.  
  214.     startpoint->kind = Leftend; 
  215.     endpoint->kind = Rightend; 
  216.     startpoint->seg = this; 
  217.     endpoint->seg = this;
  218.  
  219.     if (endpoint->x != startpoint->x)
  220.     {
  221.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  222.       yshift = startpoint->y - slope * startpoint->x;
  223.  
  224.       startpoint->x -= EPS;
  225.       startpoint->y -= EPS * slope;
  226.       endpoint->x += EPS;
  227.       endpoint->y += EPS * slope;
  228.     }
  229.     else //vertical segment
  230.     { startpoint->y -= EPS;
  231.       endpoint->y   += EPS;
  232.      }
  233.   }
  234.  
  235.  
  236. static double x_sweep;
  237. static double y_sweep;
  238.  
  239.  
  240. static int compare(segment& s1,segment& s2)
  241. {
  242.   double y1 = get_slope(s1)*x_sweep+get_yshift(s1);
  243.   double y2 = get_slope(s2)*x_sweep+get_yshift(s2);
  244.  
  245.   double diff = y1-y2;
  246.   if (diff >  EPS2 ) return  1;
  247.   if (diff < -EPS2 ) return -1;
  248.  
  249.   if (get_slope(s1) == get_slope(s2)) 
  250.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  251.  
  252.   if (y1 <= y_sweep+EPS2)
  253.         return compare(get_slope(s1),get_slope(s2));
  254.   else
  255.         return compare(get_slope(s2),get_slope(s1));
  256.  
  257. }
  258.  
  259.  
  260.  
  261. static priority_queue<seq_item,point> X_structure;
  262.  
  263. static sortseq<segment,pq_item> Y_structure;
  264.  
  265.  
  266. bool intersection(segment seg1,segment seg2, point& inter)
  267. {
  268.   if (seg1->slope == seg2->slope)
  269.     return false;
  270.   else
  271.   { 
  272.     double cx = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  273.  
  274.     if (cx <= x_sweep) return false;
  275.  
  276.     if (seg1->startpoint->x > cx || seg2->startpoint->x > cx ||
  277.         seg1->endpoint->x < cx || seg2->endpoint->x < cx ) return false;
  278.  
  279.     inter = new POINT(cx,seg1->slope * cx + seg1->yshift);
  280.  
  281.     return true;
  282.   }
  283. }
  284.  
  285.  
  286.  
  287. inline pq_item Xinsert(seq_item i, point p) 
  288. { return X_structure.insert(i,p); }
  289.  
  290.  
  291. inline point Xdelete(pq_item i) 
  292. { point p = X_structure.inf(i);
  293.   X_structure.del_item(i);
  294.   return p;
  295.  }
  296.  
  297.  
  298. void random_planar_graph(graph& G, int m)
  299. { node_array<double> xcoord;
  300.   node_array<double> ycoord;
  301.   random_planar_graph(G,xcoord,ycoord,m);
  302.  }
  303.  
  304. void random_planar_graph(graph& G, node_array<double>& xcoord,
  305.                                    node_array<double>& ycoord, int n)
  306. {
  307.   point    p,inter;
  308.   segment  seg, l,lsit,lpred,lsucc,lpredpred;
  309.   pq_item  pqit,pxmin;
  310.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  311.  
  312.   int MAX_X = 1000;
  313.   int MAX_Y = 1000;
  314.  
  315.   int N = int(2.5*sqrt(n)); // number of random segments
  316.  
  317.   xcoord.init(G,n,0);
  318.   ycoord.init(G,n,0);
  319.  
  320.  
  321.   int count=1;
  322.  
  323.   //initialization of the X-structure
  324.  
  325.   for (int i = 0; i < N; i++)
  326.    { point p = new POINT(random(0,MAX_X/3), random(0,MAX_Y));
  327.      point q = new POINT(random(2*MAX_X/3,MAX_X), random(0,MAX_Y));
  328.      seg = new SEGMENT(p,q,0,count++);
  329.      Xinsert(nil,get_startpoint(seg));
  330.    }
  331.  
  332.   count = 0;
  333.  
  334.   x_sweep = -MAXINT;
  335.   y_sweep = -MAXINT;
  336.  
  337.  
  338.   while( !X_structure.empty() && G.number_of_nodes() < n)
  339.   {
  340.     pxmin = X_structure.find_min();
  341.     p = X_structure.inf(pxmin);
  342.  
  343.     sitmin = X_structure.key(pxmin);
  344.  
  345.     Xdelete(pxmin);
  346.  
  347.  
  348.  
  349.     if (sitmin == nil) //left endpoint
  350.     { 
  351.       l = get_seg(p); 
  352.  
  353.       x_sweep = get_x(p);
  354.       y_sweep = get_y(p);
  355.  
  356.  
  357.       sit = Y_structure.insert(l,nil);
  358.  
  359.       Xinsert(sit,get_endpoint(l));
  360.  
  361.       sitpred = Y_structure.pred(sit);
  362.       sitsucc = Y_structure.succ(sit);
  363.  
  364.       if (sitpred != nil) 
  365.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  366.           delete Xdelete(pqit);
  367.  
  368.         lpred = Y_structure.key(sitpred);
  369.  
  370.         Y_structure.change_inf(sitpred,nil);
  371.  
  372.         if (intersection(lpred,l,inter))
  373.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  374.       }
  375.  
  376.  
  377.       if (sitsucc != nil)
  378.       { lsucc = Y_structure.key(sitsucc);
  379.         if (intersection(lsucc,l,inter))
  380.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  381.       }
  382.  
  383.     }
  384.     else if (get_kind(p) == Rightend)
  385.          //right endpoint
  386.          { 
  387.            x_sweep = get_x(p);
  388.            y_sweep = get_y(p);
  389.  
  390.            sit = sitmin;
  391.  
  392.            sitpred = Y_structure.pred(sit);
  393.            sitsucc = Y_structure.succ(sit);
  394.  
  395.            segment seg = Y_structure.key(sit);
  396.  
  397.            Y_structure.del_item(sit);
  398.  
  399.            delete seg;
  400.  
  401.            if((sitpred != nil)&&(sitsucc != nil))
  402.            {
  403.              lpred = Y_structure.key(sitpred);
  404.              lsucc = Y_structure.key(sitsucc);
  405.              if (intersection(lsucc,lpred,inter))
  406.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  407.            }
  408.          }
  409.          else // intersection point p
  410.          { 
  411.            node w = G.new_node();
  412.  
  413.            xcoord[w] = get_x(p);
  414.            ycoord[w] = get_y(p);
  415.  
  416.            count++;
  417.  
  418.            /* Let L = list of all lines intersecting in p 
  419.  
  420.               we compute sit     = L.head();
  421.               and        sitpred = L.tail();
  422.  
  423.               by scanning the Y_structure in both directions 
  424.               starting at sitmin;
  425.  
  426.            */
  427.  
  428.            /* search for sitpred upwards from sitmin: */
  429.  
  430.            Y_structure.change_inf(sitmin,nil);
  431.  
  432.            sitpred = Y_structure.succ(sitmin);
  433.  
  434.  
  435.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  436.            { point q = X_structure.inf(pqit);
  437.              if (compare(p,q) != 0) break; 
  438.              X_structure.del_item(pqit);
  439.              Y_structure.change_inf(sitpred,nil);
  440.              sitpred = Y_structure.succ(sitpred);
  441.             }
  442.  
  443.  
  444.            /* search for sit downwards from sitmin: */
  445.  
  446.            sit = sitmin;
  447.  
  448.            seq_item sit1;
  449.            
  450.            while ((sit1=Y_structure.pred(sit)) != nil)
  451.            { pqit = Y_structure.inf(sit1);
  452.              if (pqit == nil) break;
  453.              point q = X_structure.inf(pqit);
  454.              if (compare(p,q) != 0) break; 
  455.              X_structure.del_item(pqit);
  456.              Y_structure.change_inf(sit1,nil);
  457.              sit = sit1;
  458.             }
  459.  
  460.  
  461.  
  462.            // insert edges to p for all segments in sit, ..., sitpred into G
  463.            // and set left node to w 
  464.  
  465.            lsit = Y_structure.key(sitpred);
  466.  
  467.            node v = get_left_node(lsit);
  468.            if (v!=nil) G.new_edge(v,w);
  469.            set_left_node(lsit,w);
  470.  
  471.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  472.            { lsit = Y_structure.key(sit1);
  473.  
  474.              v = get_left_node(lsit);
  475.              if (v!=nil) G.new_edge(v,w);
  476.              set_left_node(lsit,w);
  477.             }
  478.  
  479.            lsit = Y_structure.key(sit);
  480.            lpred=Y_structure.key(sitpred);
  481.            sitpredpred = Y_structure.pred(sit);
  482.            sitsucc=Y_structure.succ(sitpred);
  483.  
  484.  
  485.            if (sitpredpred != nil)
  486.             { 
  487.               lpredpred=Y_structure.key(sitpredpred);
  488.  
  489.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  490.                 delete Xdelete(pqit);
  491.  
  492.               Y_structure.change_inf(sitpredpred,nil);
  493.  
  494.  
  495.               if (intersection(lpred,lpredpred,inter))
  496.                 Y_structure.change_inf(sitpredpred,
  497.                                        Xinsert(sitpredpred,inter));
  498.              }
  499.  
  500.  
  501.            if (sitsucc != nil)
  502.             {
  503.               lsucc=Y_structure.key(sitsucc);
  504.  
  505.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  506.                 delete Xdelete(pqit);
  507.                  
  508.               Y_structure.change_inf(sitpred,nil);
  509.  
  510.               if (intersection(lsucc,lsit,inter))
  511.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  512.              }
  513.  
  514.  
  515. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  516.  
  517.            x_sweep = get_x(p);
  518.            y_sweep = get_y(p);
  519.  
  520.            Y_structure.reverse_items(sit,sitpred);
  521.  
  522.           delete p;
  523.  
  524.          } // intersection
  525.  
  526.   }
  527.  
  528.   X_structure.clear();
  529.   Y_structure.clear();
  530.  
  531.  
  532.  
  533.   // normalize x and y coordinates 
  534.  
  535.   node v;
  536.   forall_nodes(v,G) 
  537.   { xcoord[v] /= (x_sweep + MAX_X/12);
  538.     ycoord[v] /= MAX_Y;
  539.    }
  540.  
  541. }
  542.  
  543.  
  544.